The conventional Web model allows clients to access Web resources (e.g., applications, services and data) via an HTTP client program, such as a Web browser. A technology referred to as Web services has been developed to provide programmatic access to Web resources. Web services may be used to provide programmatic access to Web resources including technology platforms (e.g., applications and services) and data (e.g., product catalogs and other databases) hosted on Web-connected computers such as Web server systems via a Web service interface. Generally speaking, a Web service interface may be configured to provide a standard, cross-platform API (Application Programming Interface) for communication between a client requesting some service to be performed and the service provider. In some implementations, a Web service interface may be configured to support the exchange of documents or messages including information describing the service request and response to that request. Such documents, or messages, may be exchanged using standardized Web protocols, such as the Hypertext Transfer Protocol (HTTP), for example, and may be formatted in a platform-independent data format, such as eXtensible Markup Language (XML), for example.
One example of a service that is provided to clients via a Web service interface is a data storage service. A typical data storage service (which may be referred to herein as an “object-redundant storage system”) may receive requests to store data objects on behalf of storage service clients, and may store those data objects using redundancy in order to provide a high level of durability for the stored data. For example, such a data storage service may replicate the objects it stores across different storage nodes to increase the likelihood that object data will survive the failure of any given storage node. In such systems, until a certain minimum number of replicas (e.g., two or three) of an object have been successfully written the write operation may not be considered to be completed. However, for a given object, the actual number of valid replicas (or instances) of that object might at some points in time be less than the target number, for a variety of reasons, and a replacement process may be invoked to correct the situation. For example, if a previously valid replica becomes inaccessible due to a failure of the device on which it was stored, the failed device may be replaced in the system, and another instance of the replica may be written to the replacement device. In some systems, each replica need not correspond to an exact copy of the object data. For example, in some object-redundant storage systems, an object may be divided into a number of portions or “shards” according to a redundant encoding scheme (such as a parity, error correction code or other scheme), such that the object data may be recreated from fewer than all of the generated portions. Typically, object-redundant storage systems may be optimized for performance characteristics, such as latency, throughput or availability.
Some object-redundant storage systems maintain multiple keymap instances, each of which provides records of the relationships between keys of objects (i.e., keys specified by clients or generated based on client-specified identifiers or other parameter values for the objects) and locators of particular instances or replicas of those objects. In storing such records, keymap instances also reflect the degree to which the objects are replicated within the storage system (e.g., how many instances of an object exist, and how they may be referenced). Multiple storage nodes may provide storage for individual instances of objects as identified by their locator, and the keymap instances must be continuously updated to reflect changes in the number, states and/or locations of those object instances. Object-redundant storage systems may also be responsible for synchronizing multiple replicas of a stored object if and when the object is updated.
While embodiments described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that the embodiments not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.